#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef int ll;
const int N = 507;

vector<int> G[N];  // 存图
ll d[N][N], t[N][N];
int n;         // 点数
int m;         // 边数
struct node {  // 用来保存
    ll val;    // 权值
    ll sec;    //  第二权值
    int id;    // 节点编号
    bool operator<(const node& o) const {
        if (val != o.val) return val > o.val;
        return sec > o.sec;
    }
};
ll dis[N];   // 从起点到i点的距离
ll tmc[N];   // 从起点到i点的时间
int num[N];  // 从起点到i点的途径点数
bool vis[N];
int fa[N];  // 经过fa[i]到i
void dij(int ori, ll d[][N], bool method) {
    memset(vis, 0, sizeof vis);  // 将所有点都标记为未访问
    fill(dis, dis + n + 1, INT_MAX);  // 把起点到所有点的距离标记为正无穷
    dis[ori] = 0;                     // 起点距离起点为零
    if (!method)
        tmc[ori] = 0;
    else
        num[ori] = 0;
    priority_queue<node> pq;  // 优先队列 小顶堆
    pq.push({0, 0, ori});
    while (!pq.empty()) {  // 堆内不为空
        int x = pq.top().id;
        pq.pop();  // 弹出堆顶节点，并将其编号存储在变量x里
        if (!vis[x]) {            // 如果x节点未访问过
            vis[x] = 1;           // 标记已访问
            for (int i : G[x]) {  // 遍历x的所有出度
                if (dis[x] + d[x][i] < dis[i] ||
                    dis[x] + d[x][i] == dis[i] &&
                        (!method && tmc[x] + t[x][i] < tmc[i] ||
                         method && num[x] + 1 < num[i])) {
                    // 如果经由x到i的距离比目前走到i的距离短
                    dis[i] = dis[x] + d[x][i];  // 则执行优化（松弛）
                    if (!method)
                        tmc[i] = tmc[x] + t[x][i];
                    else
                        num[i] = num[x] + 1;
                    fa[i] = x;
                    pq.push({dis[i], (method ? num[i] : tmc[i]), i});
                }
            }
        }
    }
}
void opt(vector<int> a) {
    while (!a.empty()) {
        cout << " -> " << a.back();
        a.pop_back();
    }
    cout << '\n';
}
int main() {
    cin >> n >> m;
    ll u, v, both, len, tm;
    rep(i, 0, n) rep(j, 0, n) d[i][j] = t[i][j] = INT_MAX;
    rep(_, 1, m) {
        cin >> u >> v >> both >> len >> tm;
        G[u].push_back(v);
        d[u][v] = min(d[u][v], len);
        t[u][v] = min(t[u][v], tm);
        if (!both) {
            swap(u, v);
            G[u].push_back(v);
            d[u][v] = min(d[u][v], len);
            t[u][v] = min(t[u][v], tm);
        }
    }

    int src, dst;
    cin >> src >> dst;

    vector<int> shortPath, quickPath;

    rep(i, 0, n) tmc[i] = INT_MAX;
    dij(src, d, 0);
    int x = dst;
    while (x != src) {
        shortPath.push_back(x);
        x = fa[x];
    }
    ll shortCost = dis[dst];

    rep(i, 0, n) num[i] = N;
    dij(src, t, 1);
    x = dst;
    while (x != src) {
        quickPath.push_back(x);
        x = fa[x];
    }
    ll quickCost = dis[dst];

    if (shortPath != quickPath) {
        cout << "Distance = " << shortCost << ": " << src;
        opt(shortPath);
        cout << "Time = " << quickCost << ": " << src;
        opt(quickPath);
    } else {
        cout << "Distance = " << shortCost << "; Time = " << quickCost << ": "
             << src;
        opt(shortPath);
    }
    return 0;
}
/*
In case the shortest path is not unique, output the fastest one among the
shortest paths, which is guaranteed to be unique. In case the fastest path is
not unique, output the one that passes through the fewest intersections, which
is guaranteed to be unique.
*/